package com.togo.algorithm.medium.design;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author taiyn
 * @Description TODO
 * @Date 下午8:16 2022/4/29
 **/
public class TTTT {

//    给定一个数组和一个目标值，打印所有的数组元素的组合使得元素的和等于目标值
//
//    Input：[4,3,5,9], target: 9
//    Output：[9], [3,3,3], [4,5]
//
//    List<List<Integer>> result = new ArrayList<>();
//    int[] array;
//    public List<List<Integer>> solve(int[] array, int target) {
//        this.array = array;
//        cur(target, new ArrayList<>());
//
//        return result;
//    }
//
//    private void cur(int target, List<Integer> list) {
//
//        for(int i = 0; i < array.length; i++) {
//
//            if(array[i] == target) {
//                list.add(array[i]);
//                List<Integer> tmp = new ArrayList<>(list);
//                result.add(tmp);
//                return;
//            } else if(target > array[i]) {
//                list.add(array[i]);
//                cur(target - array[i]), list);
//                list.removeLast();
//            }
//        }
//    }
//
//
//------
//
//    给定一个二维素组，寻找最长递增子串（可上下左右移动），要求非递归实现
//[9,   4,   5,  1]
//        [10,  6,   7,  9]
//        [2,   7,   8,  2]
//        [3,   4,   9, 10]
//
//        4->5->7->8->9->10
//
//
//    public int solve(int[][] array) {
//
//        int[][] dp = new int[array.length][array[0].length];
//        // 每个位置默认1
//        set dp to 1;
//
//        int result = 1;
//        for(int i = 0; i < array.length; i++){
//            for(int j = 0; j < array[0].length; j++){
//
//                int top = 1;
//                if(i > 1 && array[i - 1][j] < array[i][j]) {
//                    top = dp[i - 1][j] + 1;
//                }
//
//                int left = 1;
//                if(j > 1 && array[i][j - 1] < array[i][j]) {
//                    left = dp[i][j - 1] + 1;
//                }
//
//                dp[i][j] = Math.max(top, left);
//                result = Math.max(dp[i][j], result);
//            }
//        }
//
//        for(int i = array.length - 1; i > -1; i--){
//            for(int j = array[0].length - 1; j > -1; j--){
//
//                int down = 1;
//                if(i > 1 && array[i + 1][j] > array[i][j]) {
//                    down = dp[i + 1][j] + 1;
//                }
//
//                int right = 1;
//                if(j > 1 && array[i][j + 1] < array[i][j]) {
//                    right = dp[i][j + 1] + 1;
//                }
//
//                dp[i][j] = Math.max(Math.max(top, left), dp[i][j]);
//                result = Math.max(dp[i][j], result);
//            }
//        }
//
//        return result;
//    }
}
